package m202405.d13;

import java.util.HashMap;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/13 16:04
 */
public class Q105 {

    public static void main(String[] args) {
        Q105 q105 = new Q105();
        q105.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
    }

    Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTree(int[] preorder, int ps, int pe, int[] inorder, int is, int ie) {
        if (ps == pe) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[ps]);
//        int rootIndex = findRootIndex(inorder, preorder[ps], is, ie);
        int rootIndex = indexMap.get(preorder[ps]);
        int offset = rootIndex - is;
        root.left = buildTree(preorder, ps + 1, ps + offset + 1, inorder, is, rootIndex);
        root.right = buildTree(preorder, ps + offset + 1, pe, inorder, rootIndex + 1, ie);
        return root;
    }

//    private int findRootIndex(int[] inorder, int target, int is, int ie) {
//        for (int i = is; i < ie; i++) {
//            if (target == inorder[i]) {
//                return i;
//            }
//        }
//        return -1;
//    }
}
